<!DOCTYPE html>
<html lang="zh">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
        <title>LeetCode0004 寻找两个正序数组的中位数 | Dirac Lee</title><meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="robots" content="noodp" />
<meta name="Description" content="Dirac Lee 的博客"><link rel="prev" href="https://diraclee.gitee.io/2020/07/cs229_lecture5/" /><link rel="next" href="https://diraclee.gitee.io/2020/07/leetcode0003/" /><link rel="canonical" href="https://diraclee.gitee.io/2020/07/leetcode0004/" />
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" />
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="theme-color" content="#ffffff"><meta property="og:title" content="LeetCode0004 寻找两个正序数组的中位数" />
<meta property="og:description" content="" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://diraclee.gitee.io/2020/07/leetcode0004/" />
<meta property="article:published_time" content="2020-07-25T00:00:00+00:00" />
<meta property="article:modified_time" content="2020-07-25T00:00:00+00:00" />
<script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "LeetCode0004 寻找两个正序数组的中位数",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/diraclee.gitee.io\/2020\/07\/leetcode0004\/"
        },"image": {
                "@type": "ImageObject",
                "url": "https:\/\/diraclee.gitee.io\/logo.png",
                "width":  800 ,
                "height":  600 
            },"genre": "posts","keywords": "二分查找","wordcount":  454 ,
        "url": "https:\/\/diraclee.gitee.io\/2020\/07\/leetcode0004\/","datePublished": "2020-07-25T00:00:00\x2b00:00","dateModified": "2020-07-25T00:00:00\x2b00:00","license": "This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.","publisher": {
                "@type": "Organization",
                "name": "xxxx",
                "logo": {
                "@type": "ImageObject",
                "url": "https:\/\/diraclee.gitee.io\/logo.png",
                "width":  127 ,
                "height":  40 
                }
            },"description": ""
    }
    </script><link rel="stylesheet" href="/css/style.min.css"><link rel="stylesheet" href="/css/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/css/lib/animate/animate.min.css"></head>
    <body><script>
            window.isDark = (window.localStorage && window.localStorage.getItem('theme')) === 'dark';
            window.isDark && document.body.classList.add('dark-theme');
        </script><div class="wrapper"><nav class="navbar">
    <div class="navbar-container">
        <div class="navbar-header animated bounceIn">
            <a href="https://diraclee.gitee.io">Dirac Lee</a>
        </div>
        <div class="navbar-menu"><a class="menu-item" href="https://diraclee.gitee.io/posts" title="">文章</a><a class="menu-item" href="https://diraclee.gitee.io/tags" title="">标签</a><a class="menu-item" href="https://diraclee.gitee.io/categories" title="">分类</a><a class="menu-item" href="https://diraclee.gitee.io/about" title="">关于</a><a class="menu-item" href="https://diraclee.gitee.io" title="English"><i class="fas fa-language fa-fw"></i></a><a href="javascript:void(0);" class="theme-switch"><i class="fas fa-adjust fa-rotate-180 fa-fw" title="切换主题"></i></a>
        </div>
    </div>
</nav><nav class="navbar-mobile">
    <div class="navbar-container">
        <div class="navbar-header">
            <div class="navbar-header-title animated bounceIn">
                <a href="https://diraclee.gitee.io">Dirac Lee</a>
            </div>
            <div class="menu-toggle" id="menu-toggle">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="navbar-menu" id="mobile-menu"><a class="menu-item" href="https://diraclee.gitee.io/posts" title="">文章</a><a class="menu-item" href="https://diraclee.gitee.io/tags" title="">标签</a><a class="menu-item" href="https://diraclee.gitee.io/categories" title="">分类</a><a class="menu-item" href="https://diraclee.gitee.io/about" title="">关于</a><a class="menu-item" href="https://diraclee.gitee.io" title="English"></a><a href="javascript:void(0);" class="theme-switch"><i class="fas fa-adjust fa-rotate-180 fa-fw" title="切换主题"></i></a>
        </div>
    </div>
</nav><main class="main">
                <div class="container"><article class="page"><h1 class="post-title animated flipInX">LeetCode0004 寻找两个正序数组的中位数</h1><div class="post-meta">
            <div class="post-meta-main"><a class="author" href="https://diraclee.gitee.io" rel="author" target="_blank">
                    <i class="fas fa-user-circle fa-fw"></i>Dirac Lee
                </a>&nbsp;<span class="post-category">收录于&nbsp;<i class="far fa-folder fa-fw"></i><a href="https://diraclee.gitee.io/categories/leetcode/">Leetcode</a>&nbsp;</span></div>
            <div class="post-meta-other"><i class="far fa-calendar-alt fa-fw"></i><time datetime=2020-07-25>2020-07-25</time>&nbsp;
                <i class="fas fa-pencil-alt fa-fw"></i>约 454 字&nbsp;
                <i class="far fa-clock fa-fw"></i>预计阅读 1 分钟&nbsp;</div>
        </div><div class="post-content"><a class="post-dummy-target" id="题目"></a><h3>题目</h3>
<p>给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。</p>
<p>请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。</p>
<p>你可以假设 nums1 和 nums2 不会同时为空。</p>
<p>示例 1:</p>
<ul>
<li><code>nums1 = [1, 3]</code></li>
<li><code>nums2 = [2]</code></li>
<li>则中位数是 <code>2.0</code></li>
</ul>
<p>示例 2:</p>
<ul>
<li><code>nums1 = [1, 2]</code></li>
<li><code>nums2 = [3, 4]</code></li>
<li>则中位数是 <code>(2 + 3)/2 = 2.5</code></li>
</ul>
<a class="post-dummy-target" id="思路"></a><h3>思路</h3>
<p>求 <code>nums1[i:]</code> 与 <code>nums2[j:]</code> 合并后从小到大排列，求第 k 个数是多少</p>
<ul>
<li><code>A[k/2] &lt; B[k/2]</code> 则
<ul>
<li><code>A[0: k/2]</code>  均小于 <code>res</code></li>
<li>删掉这部分</li>
</ul>
</li>
<li><code>A[k/2] &gt; B[k/2]</code> 则
<ul>
<li><code>B[0: k/2]</code>  均小于 <code>res</code></li>
<li>删掉这部分</li>
</ul>
</li>
<li><code>A[k/2] == B[k/2]</code> 则
<ul>
<li>恰好是 <code>res</code></li>
<li>返回它</li>
</ul>
</li>
</ul>
<p>然后分别讨论总个数为奇数和偶数的情况</p>
<a class="post-dummy-target" id="c代码"></a><h3>C++代码</h3>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span><span class="lnt">32
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-c++" data-lang="c++"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">double</span> <span class="n">findMedianSortedArrays</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums1</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums2</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">tot</span> <span class="o">=</span> <span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">+</span> <span class="n">nums2</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">tot</span> <span class="o">%</span> <span class="mi">2</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
            <span class="kt">int</span> <span class="n">left</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">nums1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">nums2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">tot</span> <span class="o">/</span> <span class="mi">2</span><span class="p">);</span>
            <span class="kt">int</span> <span class="n">right</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">nums1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">nums2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">tot</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
            <span class="k">return</span> <span class="p">(</span><span class="n">left</span> <span class="o">+</span> <span class="n">right</span><span class="p">)</span> <span class="o">/</span> <span class="mf">2.0</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="k">return</span> <span class="nf">find</span><span class="p">(</span><span class="n">nums1</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">nums2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">tot</span> <span class="o">/</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">}</span>

    <span class="c1">// nums1[i..] 和 nums2[j..] 组合之后的中位数
</span><span class="c1"></span>    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">i</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums2</span><span class="p">,</span> <span class="kt">int</span> <span class="n">j</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="n">i</span> <span class="o">&gt;</span> <span class="n">nums2</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="n">j</span><span class="p">)</span> <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">nums2</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">nums1</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">k</span><span class="p">);</span>  <span class="c1">// 默认第一个序列更短
</span><span class="c1"></span>        
        <span class="k">if</span> <span class="p">(</span><span class="n">k</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="k">return</span> <span class="n">nums2</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>  <span class="c1">// 第一个序列为空的情况
</span><span class="c1"></span>            <span class="k">else</span> <span class="k">return</span> <span class="n">min</span><span class="p">(</span><span class="n">nums1</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="n">nums2</span><span class="p">[</span><span class="n">j</span><span class="p">]);</span>
        <span class="p">}</span>

        <span class="k">if</span> <span class="p">(</span><span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">==</span> <span class="n">i</span><span class="p">)</span> <span class="k">return</span> <span class="n">nums2</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="n">k</span> <span class="o">-</span> <span class="mi">1</span><span class="p">];</span>  <span class="c1">// 第一个序列为空的情况
</span><span class="c1"></span>        
        <span class="kt">int</span> <span class="n">si</span> <span class="o">=</span> <span class="n">min</span><span class="p">((</span><span class="kt">int</span><span class="p">)</span><span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">(),</span> <span class="n">i</span> <span class="o">+</span> <span class="n">k</span> <span class="o">/</span> <span class="mi">2</span><span class="p">);</span>  
        <span class="kt">int</span> <span class="n">sj</span> <span class="o">=</span> <span class="n">j</span> <span class="o">+</span> <span class="n">k</span> <span class="o">-</span> <span class="n">k</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>                      
        <span class="k">if</span> <span class="p">(</span><span class="n">nums1</span><span class="p">[</span><span class="n">si</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">nums2</span><span class="p">[</span><span class="n">sj</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span>   <span class="c1">// A[k/2] &gt; B[k/2]
</span><span class="c1"></span>            <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">nums1</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">nums2</span><span class="p">,</span> <span class="n">sj</span><span class="p">,</span> <span class="n">k</span> <span class="o">-</span> <span class="p">(</span><span class="n">sj</span> <span class="o">-</span> <span class="n">j</span><span class="p">));</span>
        <span class="k">else</span>
            <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">nums1</span><span class="p">,</span> <span class="n">si</span><span class="p">,</span> <span class="n">nums2</span><span class="p">,</span> <span class="n">j</span><span class="p">,</span> <span class="n">k</span> <span class="o">-</span> <span class="p">(</span><span class="n">si</span> <span class="o">-</span> <span class="n">i</span><span class="p">));</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div></div><div class="post-footer" id="post-footer">
    <div class="post-info">
        <div class="post-info-line">
            <div class="post-info-mod">
                <span>本文于 2020-07-25 更新</span>
            </div>
            <div class="post-info-license"></div>
        </div>
        <div class="post-info-line">
            <div class="post-info-md"></div>
            <div class="post-info-share"><span><a href="//www.linkedin.com/shareArticle?url=https%3a%2f%2fdiraclee.gitee.io%2f2020%2f07%2fleetcode0004%2f&amp;title=LeetCode0004%20%e5%af%bb%e6%89%be%e4%b8%a4%e4%b8%aa%e6%ad%a3%e5%ba%8f%e6%95%b0%e7%bb%84%e7%9a%84%e4%b8%ad%e4%bd%8d%e6%95%b0" target="_blank" title="分享到 LinkedIn">
            <i class="fab fa-linkedin fa-fw"></i>
        </a><a href="//service.weibo.com/share/share.php?url=https%3a%2f%2fdiraclee.gitee.io%2f2020%2f07%2fleetcode0004%2f&amp;appkey=&amp;title=LeetCode0004%20%e5%af%bb%e6%89%be%e4%b8%a4%e4%b8%aa%e6%ad%a3%e5%ba%8f%e6%95%b0%e7%bb%84%e7%9a%84%e4%b8%ad%e4%bd%8d%e6%95%b0" target="_blank" title="分享到 Weibo">
            <i class="fab fa-weibo fa-fw"></i>
        </a></span></div>
        </div>
    </div>

    <div class="post-info-more">
        <section><span class="tag">
                        <a href="https://diraclee.gitee.io/tags/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/"><i class="fas fa-tag fa-fw"></i>&nbsp;二分查找</a>&nbsp;
                    </span></section>
        <section>
            <span><a href="javascript:window.history.back();">返回</a></span>&nbsp;|&nbsp;<span><a href="https://diraclee.gitee.io">主页</a></span>
        </section>
    </div>

    <div class="post-nav"><a href="https://diraclee.gitee.io/2020/07/cs229_lecture5/" class="prev" rel="prev" title="cs229 第五节"><i class="fas fa-angle-left fa-fw"></i>cs229 第五节</a>
            <a href="https://diraclee.gitee.io/2020/07/leetcode0003/" class="next" rel="next" title="LeetCode0003 无重复字符的最长子串">LeetCode0003 无重复字符的最长子串<i class="fas fa-angle-right fa-fw"></i></a></div>
</div><div class="post-comment"></div>
    </article></div>
            </main><footer class="footer">
    <div class="copyright"><div class="copyright-line">由 <a href="https://gohugo.io/" target="_blank" rel="external nofollow noopener noreffer">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/dillonzq/LoveIt" target="_blank" rel="external nofollow noopener noreffer">LoveIt<i class="far fa-heart fa-fw"></i></a>
        </div>

        <div class="copyright-line"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2020</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="https://diraclee.gitee.io" target="_blank">Dirac Lee</a></span>&nbsp;|&nbsp;<span class="license"><a rel="license external nofollow noopener noreffer" href="https://creativecommons.org/licenses/by-nc/4.0/" target="_blank">CC BY-NC 4.0</a></span></div>
    </div>
</footer></div><a href="#" class="dynamic-to-top" id="dynamic-to-top" data-scroll>
            <span>&nbsp;</span>
        </a><script src="/js/lib/jquery/jquery.slim.min.js"></script><script src="/js/lib/lazysizes/lazysizes.min.js"></script><script src="/js/lib/smooth-scroll/smooth-scroll.polyfills.min.js"></script><script>window.scroll = new SmoothScroll('[data-scroll]', {speed: 300, speedAsDuration: true});</script><link rel="stylesheet" href="/css/lib/katex/katex.min.css"><script src="/js/lib/katex/katex.min.js"></script><script defer src="/js/lib/katex/auto-render.min.js"></script><link rel="stylesheet" href="/css/lib/katex/copy-tex.min.css"><script defer src="/js/lib/katex/copy-tex.min.js"></script><script defer src="/js/lib/katex/mhchem.min.js"></script><script>
        document.addEventListener("DOMContentLoaded", function () {
            renderMathInElement(document.body, {
                delimiters: [
                    { left: "$$", right: "$$", display: true },
                    { left: "\\(", right: "\\)", display: false },
                    { left: "\\[", right: "\\]", display: true },{ left: "$", right: "$", display: false },]
            });
        });
    </script><script src="/js/blog.min.js"></script></body>
</html>